|
BFS，全称Breadth First Search，宽度优先搜索算法（又称广度优先搜索）。 运用队列先进先出的特点来遍历所有情况。由于是宽度优先，所以会一层一层遍历所有情况，可以以此特性来求解搜索路径的最小值。
伪代码（我理解中的）：
/*
* 首先先定义需要搜索的每一个点或者每一种情况，
* （如需求最小路径，则添加当前步数step）
*/
struct location{
int x; //定义需要搜索位置的信息。
int y; //如搜索迷宫，则定义横纵坐标。
int step; //到达当前位置所进行的步数。
};
location lo[N][N];
int cmp[] = {n1,n2,m1,m2,k1,k2,z1,z2} // 所有满足情况的判断条件集合，也可以写成if语句
//但是会增加很多代码量。
int flag[N][N]; //当一个点被遍历以后，为其做上标记，防止重复遍历，极大减小运算量。
int bfs(){
queue q; //建立一个队列；
location cur,next; //该队列中只需要两个变量即可，当前变量和当前变量的子变量。参考二叉树之类~
int fx,fy; //作为中间变量，用以判断该位置是否满足边界条件或需求，同时用以赋值。
cur.x = first.x;
cur.y = first.y;
cur.step = 0; //初始化当前变量。
q.push(cur); //将当前变量弹进队列。初始化完毕。
flag[fist.x][first.y] = 1; //起点位置标记为已经走过。
while(!q.empty()){ //当队列不为空，表示符合条件的位置还没有访问完。
cur = q.front();
q.pop(); //cur指向队列首，并将其弹出。初始化虽然指向过，但是循环体需要！
if(满足搜索条件){
return 需要的结果； //找到满足的结果，提前结束循环。
}
//若不满足，则找出cur对象的子对象next，将他弹入队列中。
for(int i = 1; i |